/LMAR=0/XLINE=3/FONT#0=BAXL30[FNT,CLT]/FONT#1=BAXM30/FONT#2=BAXB30[FNT,CLT]/FONT#5=GACS25/FONT#3=SUB/FONT#4=SUP/FONT#7=SYMB30[FNT,CLT]

␈↓ ↓H␈↓␈↓ ¬πSTANFORD UNIVERSITY

␈↓ ↓H␈↓CS206  ␈↓ βZCOMPUTING WITH SYMBOLIC EXPRESSIONS  ␈↓ 
0FALL 1978

␈↓ ↓H␈↓␈↓ ¬DPROBLEM SET  1
␈↓ ↓H␈↓␈↓ ¬[Due  October 24

␈↓ ↓H␈↓        Write␈αLISP␈αprograms␈αfor␈αeach␈αof␈αthe␈α
functions␈αdescribed␈αbelow.␈α For␈αeach␈αprogram␈αturn␈α
in
␈↓ ↓H␈↓the following:

␈↓ ↓H␈↓␈↓ βλ1.  The internal form of the program.
␈↓ ↓H␈↓␈↓ βλ2.  The corresponding external form recursive definition.
␈↓ ↓H␈↓␈↓ βλ3.  A description of how the progam works and why.
␈↓ ↓H␈↓␈↓ βλ4.  Output from test runs on a variety of input.

␈↓ ↓H␈↓        Late assignments are discouraged and will not be accepted after the solutions appear.


␈↓ ↓H␈↓αFunction descriptions.

␈↓ ↓H␈↓1.␈α⊂␈↓↓sizesort[u]␈↓␈α⊂returns␈α∂a␈α⊂permutation␈α⊂of␈α⊂␈↓↓u␈↓␈α∂which␈α⊂has␈α⊂smaller␈α∂length␈α⊂sublists␈α⊂before␈α⊂larger␈α∂ones.
␈↓ ↓H␈↓␈↓ α(Atomic␈αelements␈α
should␈αbe␈αconsidered␈α
to␈αhave␈α0␈α
length.␈α Sublists␈αof␈α
the␈αsame␈αsize␈α
can␈αbe
␈↓ ↓H␈↓␈↓ α(in any order.  The following is one i/o pair which satisfies the function definition.

␈↓ ↓H␈↓␈↓ αG␈↓↓sizesort[␈↓¬(H (D E) (F G H) (D F) B A)␈↓↓] = ␈↓¬(H B A (D E) (D F) (F G H))␈↓↓.␈↓ 

␈↓ ↓H␈↓2.␈α
␈↓↓powerset[u]␈↓␈α
returns␈α
the␈α
power-set␈α
of␈α
set␈α
␈↓↓u.␈↓␈α
 A␈α
set␈α
is␈α
represented␈α
as␈α
a␈α
list␈α
of␈α
elements␈α
with␈α
no
␈↓ ↓H␈↓␈↓ α(repetitions.␈α⊂Order␈α⊂within␈α∂the␈α⊂list␈α⊂is␈α∂unimportant.␈α⊂ The␈α⊂following␈α∂is␈α⊂one␈α⊂i/o␈α⊂pair␈α∂which
␈↓ ↓H␈↓␈↓ α(satisfies the function definition.

␈↓ ↓H␈↓␈↓ αg␈↓↓powerset[␈↓¬(A B C)␈↓↓] = ␈↓¬((A B C) (A B) (A C) (A) (B C) (B) (C) ())␈↓↓.␈↓ 

␈↓ ↓H␈↓3.␈α∂␈↓↓allsub[u,v]␈↓␈α⊂returns␈α∂a␈α⊂list␈α∂giving␈α⊂all␈α∂occurrences␈α⊂of␈α∂the␈α∂list␈α⊂␈↓↓u␈↓␈α∂as␈α⊂a␈α∂toplevel␈α⊂sublist␈α∂of␈α⊂␈↓↓v.␈↓␈α∂An
␈↓ ↓H␈↓␈↓ α(occurrence␈α∂is␈α∂given␈α∂by␈α∂the␈α∂number␈α∂denoting␈α∂the␈α∂position␈α∂in␈α∂␈↓↓v␈↓␈α∂where␈α∂the␈α∂match␈α∂begins.
␈↓ ↓H␈↓␈↓ α(The following is one i/o pair which satisfies the function definition.

␈↓ ↓H␈↓␈↓ ∧0␈↓↓allsub[␈↓¬(A A),(A A A A A)␈↓↓] = ␈↓¬(1 2 3 4)␈↓↓.␈↓ 

␈↓ ↓H␈↓4.␈α
␈↓↓allsub![u,v]␈↓␈α
returns␈α
a␈αlist␈α
giving␈α
all␈α
occurrences␈α
of␈αthe␈α
list␈α
␈↓↓u␈↓␈α
as␈α
a␈αsublist␈α
of␈α
␈↓↓v,␈↓␈α
at␈α
any␈αlevel.␈α
 Now
␈↓ ↓H␈↓␈↓ α(an␈αoccurrence␈αis␈αa␈αlist␈αof␈αnumbers␈αgiving␈αthe␈αpath␈αto␈αbeginning␈αto␈αsublist␈αoccurrence.␈αThe
␈↓ ↓H␈↓␈↓ α(following is one i/o pair which satisfies the function definition.

␈↓ ↓H␈↓␈↓ β∧␈↓↓allsub![␈↓¬(A),(A (B (A (B (A)))))␈↓↓] = ␈↓¬((1) (2 2 1) (2 2 2 2 1))␈↓↓␈↓ 

␈↓ ↓H␈↓5.␈α ␈↓↓mapexp␈↓␈αtakes␈αas␈αarguments␈α
an␈αS-expression,␈αa␈αunary␈αfunction␈α
␈↓↓f1␈↓␈αand␈αa␈αbinary␈αfunction␈α␈↓↓f2.␈↓␈α
 It
␈↓ ↓H␈↓␈↓ α(takes␈αthe␈αS-expression␈αapart,␈αapplies␈αthe␈α
unary␈αfunction␈αto␈αeach␈αatom␈αand␈αputs␈α
the␈αresult
␈↓ ↓H␈↓␈↓ α(back␈αtogether␈αusing␈αthe␈αbinary␈αfunction␈αThus␈αif␈α␈↓↓f1␈↓␈αis␈αthe␈αidentity␈αfunction␈αand␈α␈↓↓f2␈↓␈αis␈α␈↓↓cons␈↓
␈↓ ↓H␈↓␈↓ α(then␈α⊃␈↓↓maptree␈↓␈α⊃returns␈α⊃a␈α⊃copy␈α⊃of␈α⊃the␈α⊃S-expression.␈α⊃ If␈α⊃␈↓↓f1␈↓␈α⊃is␈α⊃␈↓↓ncons␈↓␈α⊃(forms␈α⊃a␈α⊃list␈α⊃of␈α⊂one
␈↓ ↓H␈↓␈↓ α(element) and ␈↓↓f2␈↓ is ␈↓↓append␈↓ then ␈↓↓maptree␈↓ returns the ␈↓↓fringe␈↓ of the S-expression.

␈↓ ↓H␈↓6.␈α Let␈αa␈α
graph␈α␈↓↓g␈↓␈αbe␈αrepresented␈α
as␈αdescribed␈αin␈α
Chapter␈αI␈αof␈αthe␈α
text␈αand␈αsuppose␈αthat␈α
whenever
␈↓ ↓H␈↓␈↓ α(there␈α
is␈αan␈α
edge␈α
from␈α␈↓↓x␈↓␈α
to␈α␈↓↓y␈↓␈α
 there␈α
is␈αalso␈α
an␈α
edge␈αfrom␈α
␈↓↓y␈↓␈αto␈α
␈↓↓x.␈↓␈α
 A␈αcomponent␈α
of␈αthe␈α
graph
␈↓ ↓H␈↓␈↓ α(is␈α∂a␈α∂collection␈α∂of␈α∂vertices␈α⊂which␈α∂are␈α∂all␈α∂connected␈α∂to␈α⊂each␈α∂other␈α∂by␈α∂edge␈α∂paths␈α⊂but␈α∂not
␈↓ ↓H␈↓␈↓ α(connected␈αto␈αany␈αvertices␈αnot␈αin␈αthis␈αcollection.␈α Write␈αa␈αfunction␈α␈↓↓components␈↓␈αto␈αdetermine
␈↓ ↓H␈↓␈↓ α(the components of a graph ␈↓↓g.␈↓
␈↓ ↓H␈↓α␈↓ αzFunctions definitions (external and internal form) for assignment 1.␈↓ ↓H␈↓␈↓ εH␈↓ 91

␈↓ ↓H␈↓1. ␈↓↓allsub[u,v]␈↓

␈↓ ↓H␈↓↓        allsub[u, v] ← allsub1[u, v, 1]

␈↓ ↓H␈↓↓        allsub1[u, v, n] ← 
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ ␈↓αn|␈↓↓v ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ ␈↓αif␈↓↓ match[u, v] ␈↓αthen␈↓↓ n . allsub1[u, ␈↓αd|␈↓↓v, add1 n]
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ allsub1[u, ␈↓αd|␈↓↓v, add1 n]

␈↓ ↓H␈↓↓        match[u, v] ← 
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ ␈↓¬T␈↓↓ ␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αn|␈↓↓v ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓ ␈↓αelse␈↓↓ ␈↓αa|␈↓↓u = ␈↓αa|␈↓↓v ∧ match[␈↓αd|␈↓↓u, ␈↓αd|␈↓↓v]

␈↓ ↓H␈↓¬        (DEFUN ALLSUB (U V) (ALLSUB1 U V 1.))

␈↓ ↓H␈↓¬        (DEFUN ALLSUB1 (U V N)
␈↓ ↓H␈↓¬               (COND ((NULL V) NIL)
␈↓ ↓H␈↓¬                     ((MATCH U V) (CONS N (ALLSUB1 U (CDR V) (ADD1 N))))
␈↓ ↓H␈↓¬                     (T (ALLSUB1 U (CDR V) (ADD1 N)))))

␈↓ ↓H␈↓¬        (DEFUN MATCH (U V)
␈↓ ↓H␈↓¬               (COND ((NULL U) T)
␈↓ ↓H␈↓¬                     ((NULL V) NIL)
␈↓ ↓H␈↓¬                     (T (AND (EQUAL (CAR U) (CAR V))
␈↓ ↓H␈↓¬                             (MATCH (CDR U) (CDR V))))))

␈↓ ↓H␈↓2. ␈↓↓allsub![u,v]␈↓

␈↓ ↓H␈↓↓        allsub![u, v] ← allsub!1[u, v, 1]

␈↓ ↓H␈↓↓        allsub!1[u, v, n] ← 
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ ␈↓αn|␈↓↓v ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ ␈↓αif␈↓↓ match[u, v] ␈↓αthen␈↓↓ <n> . allsub!1[u, ␈↓αd|␈↓↓v, add1 n]
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αat|␈↓↓␈↓αa|␈↓↓v ␈↓αthen␈↓↓ allsub!1[u, ␈↓αd|␈↓↓v, add1 n]
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ tack[n, allsub![u, ␈↓αa|␈↓↓v]] * allsub!1[u, ␈↓αd|␈↓↓v, add1 n]

␈↓ ↓H␈↓↓        tack[n, w] ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓w ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓ ␈↓αelse␈↓↓ [n . ␈↓αa|␈↓↓w] . tack[n, ␈↓αd|␈↓↓w]

␈↓ ↓H␈↓¬        (DEFUN ALLSUB! (U V) (ALLSUB!1 U V 1.))

␈↓ ↓H␈↓¬        (DEFUN ALLSUB!1 (U V N)
␈↓ ↓H␈↓¬               (COND ((NULL V) NIL)
␈↓ ↓H␈↓¬                     ((MATCH U V)
␈↓ ↓H␈↓¬                      (CONS (LIST N) (ALLSUB!1 U (CDR V) (ADD1 N))))
␈↓ ↓H␈↓¬                     ((ATOM (CAR V)) (ALLSUB!1 U (CDR V) (ADD1 N)))
␈↓ ↓H␈↓¬                     (T (APPEND (TACK N (ALLSUB! U (CAR V)))
␈↓ ↓H␈↓¬                                (ALLSUB!1 U (CDR V) (ADD1 N))))))

␈↓ ↓H␈↓¬        (DEFUN TACK (N W)
␈↓ ↓H␈↓¬               (COND ((NULL W) NIL)
␈↓ ↓H␈↓¬                     (T (CONS (CONS N (CAR W)) (TACK N (CDR W))))))

␈↓ ↓H␈↓3.  ␈↓↓mapexp␈↓ [or ␈↓↓maptree␈↓]

␈↓ ↓H␈↓↓        maptree[s, f1, f2] ← 
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ ␈↓αat|␈↓↓s ␈↓αthen␈↓↓ f1 s
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ f2[maptree[␈↓αa|␈↓↓s, f1, f2], maptree[␈↓αd|␈↓↓s, f1, f2]]
␈↓ ↓H␈↓¬        (DEFUN MAPTREE (S F1 F2)␈↓ ↓H␈↓␈↓ εH␈↓ 92
␈↓ ↓H␈↓¬               (COND ((ATOM S) (F1 S))
␈↓ ↓H␈↓¬                     (T (F2 (MAPTREE (CAR S) F1 F2)
␈↓ ↓H␈↓¬                            (MAPTREE (CDR S) F1 F2)))))

␈↓ ↓H␈↓4. ␈↓↓ncomps␈↓

␈↓ ↓H␈↓↓        ncomps g ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓g ␈↓αthen␈↓↓ 0 ␈↓αelse␈↓↓ add1 ncomps scan[␈↓αd|␈↓↓g, ␈↓¬NIL␈↓↓, ␈↓αa|␈↓↓g, ␈↓¬NIL␈↓↓]

␈↓ ↓H␈↓↓        scan[g, h, u, flag] ← 
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ ␈↓αn|␈↓↓g ␈↓αthen␈↓↓ [␈↓αif␈↓↓ ␈↓αn|␈↓↓flag ∨ ␈↓αn|␈↓↓h ␈↓αthen␈↓↓ h ␈↓αelse␈↓↓ scan[h, ␈↓¬NIL␈↓↓, u, ␈↓¬NIL␈↓↓]]
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αn|␈↓↓[␈↓αaa|␈↓↓g ε u] ␈↓αthen␈↓↓ scan[␈↓αd|␈↓↓g, ␈↓αa|␈↓↓g . h, u, flag]
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ scan[␈↓αd|␈↓↓g, h, u * ␈↓αa|␈↓↓g, ␈↓¬T␈↓↓]

␈↓ ↓H␈↓¬(DEFUN NCOMPS (G)
␈↓ ↓H␈↓¬       (COND ((NULL G) 0.)
␈↓ ↓H␈↓¬             (T (ADD1 (NCOMPS (SCAN (CDR G) NIL (CAR G) NIL))))))

␈↓ ↓H␈↓¬(DEFUN SCAN (G H U FLAG)
␈↓ ↓H␈↓¬       (COND ((NULL G)
␈↓ ↓H␈↓¬              (COND ((OR (NULL FLAG) (NULL H)) H)
␈↓ ↓H␈↓¬                    (T (SCAN H NIL U NIL))))
␈↓ ↓H␈↓¬             ((NULL (MEMBER (CAAR G) U))
␈↓ ↓H␈↓¬              (SCAN (CDR G) (CONS (CAR G) H) U FLAG))
␈↓ ↓H␈↓¬             (T (SCAN (CDR G) H (APPEND U (CAR G)) T))))

␈↓ ↓H␈↓5. ␈↓↓partition[u,n]␈↓

␈↓ ↓H␈↓↓        partition[u, n] ← 
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ length u < n ␈↓αthen␈↓↓ ␈↓¬(INVALID N)␈↓↓ ␈↓αelse␈↓↓ part1[<␈↓αa|␈↓↓u>, ␈↓αd|␈↓↓u, sub1 n]

␈↓ ↓H␈↓↓        part1[u, v, n] ← 
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ ␈↓αn|␈↓↓v ␈↓αthen␈↓↓ [␈↓αif␈↓↓ zerop n ␈↓αthen␈↓↓ <<u>> ␈↓αelse␈↓↓ ␈↓¬NIL␈↓↓]
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ tack[u, part1[<␈↓αa|␈↓↓v>, ␈↓αd|␈↓↓v, sub1 n]]
␈↓ ↓H␈↓↓                  * part1[u * <␈↓αa|␈↓↓v>, ␈↓αd|␈↓↓v, n]

␈↓ ↓H␈↓↓        testpart[v, u] ← 
␈↓ ↓H␈↓↓            ␈↓αif␈↓↓ ␈↓αn|␈↓↓v ␈↓αthen␈↓↓ ␈↓¬T␈↓↓
␈↓ ↓H␈↓↓            ␈↓αelse␈↓↓ combine ␈↓αa|␈↓↓v = u ∧ testpart[␈↓αd|␈↓↓v, u] 

␈↓ ↓H␈↓↓        combine w ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓w ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓ ␈↓αelse␈↓↓ ␈↓αa|␈↓↓w * combine ␈↓αd|␈↓↓w

␈↓ ↓H␈↓¬        (DEFUN PARTITION (U N)
␈↓ ↓H␈↓¬               (COND ((LESSP (LENGTH U) N) '(INVALID N))
␈↓ ↓H␈↓¬                     (T (PART1 (LIST (CAR U)) (CDR U) (SUB1 N)))))

␈↓ ↓H␈↓¬        (DEFUN PART1 (U V N)
␈↓ ↓H␈↓¬               (COND ((NULL V) (COND ((ZEROP N) (LIST (LIST U))) (T NIL)))
␈↓ ↓H␈↓¬                     (T (APPEND (TACK U
␈↓ ↓H␈↓¬                                      (PART1 (LIST (CAR V)) (CDR V) (SUB1 N)))
␈↓ ↓H␈↓¬                                (PART1 (APPEND U (LIST (CAR V)))
␈↓ ↓H␈↓¬                                       (CDR V)
␈↓ ↓H␈↓¬                                       N)))))

␈↓ ↓H␈↓¬        (DEFUN LINK (U W)
␈↓ ↓H␈↓¬               (COND ((NULL W) NIL)
␈↓ ↓H␈↓¬                     (T (CONS (CONS U (CAR W)) (LINK U (CDR W))))))

␈↓ ↓H␈↓¬        (DEFUN TESTPART (V U)
␈↓ ↓H␈↓¬               (COND ((NULL V) T)
␈↓ ↓H␈↓¬                     ((AND (EQUAL (COMBINE (CAR V)) U)␈↓ ↓H␈↓␈↓ εH␈↓ 93
␈↓ ↓H␈↓¬                           (TESTPART (CDR V) U)))))

␈↓ ↓H␈↓¬        (DEFUN COMBINE (W)
␈↓ ↓H␈↓¬               (COND ((NULL W) NIL) (T (APPEND (CAR W) (COMBINE (CDR W))))))